// 84. 分隔链表
// https://leetcode.cn/problems/partition-list/description/
// 链表

// 思路
// 这题看上去也很难，但参考官方题解后，原来是可以《新增链表》来实现的
// 所以没必要死改原链表，这做法太吃力了，后期也容易看不懂
// 新增链表时，需要使用 new ListNode()方法，记得将function ListNode(val, next)放开

/**
输入：head = [1,4,3,2,5,2], x = 3
输出：[1,2,2,4,3,5]

输入：head = [2,1], x = 2
输出：[1,2]
 */

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} head
 * @param {number} x
 * @return {ListNode}
 */
var partition = function (head, x) {
    // 定义两个ListNode
    // 将<x的放入low
    // 将>=x的放入high
    // 最后链接的时候处理一下，把两个ListNode的头元素拿掉
    let lowSort = new ListNode(-1);
    let lowPointer = lowSort;

    let highSort = new ListNode(x);
    let highPointer = highSort;

    let cur = head;
    while (cur.val) {
        if (cur.val < x) {
            lowPointer.next = new ListNode(cur.val);
            lowPointer = lowPointer.next;

            flat(lowSort);
        } else {
            highPointer.next = new ListNode(cur.val);
            highPointer = highPointer.next;

            flat(highSort);
        }

        if (cur.next) cur = cur.next;
        else break;
    }

    // 链接low和high
    lowPointer.next = highSort.next;
    return lowSort.next;
};

function ListNode(val, next) {
    this.val = val === undefined ? 0 : val;
    this.next = next === undefined ? null : next;
}

function listNodes(arr) {
    console.log(`[listNode] arr is ${JSON.stringify(arr)}`);
    if (!arr || arr.length < 1) {
        return null;
    }

    let ret = {
        val: null,
        next: null,
    };
    let temp = ret;
    for (let i = 0; i < arr.length; i++) {
        temp.val = arr[i];
        temp.next = null;
        if (i < arr.length - 1) {
            temp.next = {
                val: null,
                next: null,
            };
        }

        temp = temp.next;
    }
    // console.log(`[listNode complete] ret is ${JSON.stringify(ret)}`);
    return ret;
}

function flat(listNode) {
    if (listNode == null) {
        console.log(`flat: node is ${JSON.stringify([])}`);
        return [];
    }

    let arr = [];
    let node = listNode;
    // console.log(`flat: node is ${JSON.stringify(node)}`);
    do {
        arr.push(node.val);
        node = node.next;
    } while (!!node && !!node.next);
    if (!!node) {
        arr.push(node.val);
    }

    console.log(`flat complete: arr is ${JSON.stringify(arr)}`);
    return arr;
}

// [1,4,3,2,5,2] -> [1,2,2,4,3,5]
flat(partition(listNodes([1, 4, 3, 2, 5, 2]), 3));
flat(partition(listNodes([1, 4, 3, 2, 5, 2]), 3));
